package com.bjsxt.datastructure.btree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class LinkedBinaryTree implements BinaryTree {

    private Node root;

    public LinkedBinaryTree() {

    }

    public LinkedBinaryTree(Node root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public int size() {
        System.out.println("二叉树节点的个数： ");
        return this.size(root);
    }

    private int size(Node node) {
        if (node != null) {
            //左子树的节点个数
            int left = this.size(node.leftChild);
            //右子树的节点个数
            int right = this.size(node.rightChild);

            return left + right + 1;
        }
        return 0;
    }

    @Override
    public int getHeight() {
        return this.getHeight(root);
    }

    private int getHeight(Node node) {
        if (node != null) {
            //左子树的高度
            int leftHeight = this.getHeight(node.leftChild);
            //右子树的高度

            int rightHeight = this.getHeight(node.rightChild);

            return Math.max(leftHeight, rightHeight) + 1;
        }
        return 0;

    }

    @Override
    public Node findKey(int value) {
        System.out.println("二叉树查找某个值： ");
        return this.findKey(value, root);
    }

    private Node findKey(Object value, Node root) {
        if (root == null) {
            return null;
        } else if (root != null && root.value == value) {
            return root;
        } else {
            Node left = this.findKey(value, root.leftChild);
            Node right = this.findKey(value, root.rightChild);
            if (left != null && left.value == value) {
                return left;
            } else if (right != null && right.value == value) {
                return right;
            } else {
                return null;
            }
        }

    }

    @Override
    public void preOrderTraverse() {
        if (root != null) {
            //1。输出节点根的值
            System.out.print(root.value + " ");

            //2。对左子树进行先序遍历
            //构建一个二叉树，根是左子树对根
            BinaryTree leftTree = new LinkedBinaryTree(root.leftChild);
            leftTree.preOrderTraverse();

            //3。对右子树进行先序遍历
            //构建一个二叉树，根是右子树的根
            BinaryTree rightTree = new LinkedBinaryTree(root.rightChild);
            rightTree.preOrderTraverse();
        }
    }

    @Override
    public void inOrderTraverse() {
        System.out.println("中序遍历");
        this.inOrderTraverse(root);
        System.out.println();

    }

    private void inOrderTraverse(Node root) {
        if (root != null) {
            //1。对左子树进行先序遍历
            //构建一个二叉树，根是左子树对根
            this.inOrderTraverse(root.leftChild);
            //2。输出节点根的值
            System.out.print(root.value + " ");
            //3。对右子树进行先序遍历
            //构建一个二叉树，根是右子树的根
            this.inOrderTraverse(root.rightChild);
        }
    }

    @Override
    public void postOrderTraverse() {
        System.out.println("后序遍历");
        this.postOrderTraverse(root);
        System.out.println();
    }

    @Override
    public void postOrderTraverse(Node node) {
        if (node != null) {
            //1.遍历左子树
            this.postOrderTraverse(node.leftChild);
            //2.遍历右子树
            this.postOrderTraverse(node.rightChild);
            //3.遍历根节点
            System.out.print(node.value + " ");
        }
    }

    @Override
    public void inOrderByStack() {
        System.out.println("中序遍历-不采用递归");
        Deque<Node> stack = new LinkedList<>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.leftChild;
            }
            if (!stack.isEmpty()) {
                current = stack.poll();
                System.out.print(current.value + "  ");
                current = current.rightChild;
            }
        }
        System.out.println();
    }

    @Override
    public void preOrderByStack() {
//        System.out.println("先序遍历-不采用递归");
//        Deque<Node> stack = new LinkedList<>();
//        Node current = root;
//        while (current != null || !stack.isEmpty()) {
//            while (current != null) {
//                stack.push(current);
//                current = current.leftChild;
//            }
//            if (!stack.isEmpty()) {
//                current = stack.poll();
//                System.out.print(current.value + " ");
//                current = current.rightChild;
//            }
//        }
//        System.out.println();

    }

    @Override
    public void postOrderByStack() {
//        System.out.println("后序遍历-不采用递归");
//        Deque<Node> stack = new LinkedList<>();
//        Node current = root;
//        while (current != null || !stack.isEmpty()) {
//            while (current != null) {
//                stack.push(current);
//                current = current.rightChild;
//            }
//            if (!stack.isEmpty()) {
//                current = stack.poll();
//                System.out.print(current.value + " ");
//                current = current.leftChild;
//            }
//        }
//        System.out.println();

    }

    @Override
    public void levelOrderByStack() {
        System.out.println("按照层次便利二叉树");
        if (root == null) {
            return;
        }
        Queue<Node> quote = new LinkedList<>();
        quote.add(root);
        while (quote.size() != 0) {
            int len = quote.size();
            for (int i = 0; i < len; i++) {
                Node temp = quote.poll();
                System.out.print(temp.value + " ");
                if (temp.leftChild != null) quote.add(temp.leftChild);
                if (temp.rightChild != null) quote.add(temp.rightChild);
            }
        }
        System.out.println();

    }
}
